//package work.rightAnswer;
//
//class Solution_52 {
//    private int count = 0;
//    public int totalNQueens(int n) {
//        //返回在nXn矩阵中，有多少种n皇后摆法
//        int[][] boards = new int[n][n];
//
//        backtracing(boards,0);
//        return count;
//    }
//
//    //遍历n*n矩阵，得出所有n皇后问题的解决方案。boards:矩阵，row:行数
//    public void backtracing(int[][] boards,int row){
//        if(row==boards.length){
//            count++;
//            return;
//        }
//
//        for (int i = 0; i < boards[row].length; i++) {
//            if(isValid(boards,row,i)){
//                boards[row][i] = 1;
//                backtracing(boards,row+1);
//                boards[row][i] = 0;
//            }
//        }
//
//    }
//
//    private boolean isValid(int[][] boards, int row, int col) {
//        //列不重复
//        for (int i = 0; i < row; i++) {
//            if(boards[i][col]==1){
//                return false;
//            }
//        }
//
//        //45°右上角
//        int i = row;
//        int j = col;
//        while (i>=0&&j<=boards[0].length-1){
//            if(boards[i][j]==1){
//                return false;
//            }
//            i--;
//            j++;
//        }
//
//
//        //135°左上角
//        i = row;
//        j = col;
//        while (i>=0&&j>=0){
//            if(boards[i][j]==1){
//                return false;
//            }
//            i--;
//            j--;
//        }
//
//
//        return true;
//    }
//}